198. 打家劫舍

https://leetcode-cn.com/problems/house-robber/

以"打家劫舍"问题为例来说明如何找到状态转移方程。

问题描述：假设你是一名专业的盗贼，要打劫一条街上的房屋。每个房屋都存放着一定数量的钱财。相邻的房屋装有防盗系统，如果同时打劫相邻的两个房屋，系统会自动报警。你需要确定在不触发警报的情况下，可以获得的最大金额。

确定最优子结构：在这个问题中，最优子结构意味着问题的最优解可以通过一系列子问题的最优解构建出来。假设我们要解决打劫第 i 个房屋的问题，我们需要考虑打劫前 i-1 个房屋的最优解。因此，问题具有最优子结构。
定义状态：在这个问题中，我们可以将问题的状态定义为打劫前 i 个房屋能够获得的最大金额。假设我们用 dp[i] 表示状态。
确定状态之间的关系：状态转移关系是关键。在打劫第 i 个房屋时，我们有两个选择：要么打劫第 i 个房屋，那么我们不能打劫第 i-1 个房屋；要么不打劫第 i 个房屋，那么我们可以打劫第 i-1 个房屋。我们需要选择这两个选择中能够获得的最大金额。因此，状态转移方程可以定义为： dp[i] = max(dp[i-2] + nums[i], dp[i-1])
定义初始条件：对于前两个房屋，我们可以直接确定最大金额。即 dp[0] = nums[0]，dp[1] = max(nums[0], nums[1])。
建立状态转移方程：通过分析问题的最优子结构和状态转移关系，我们可以得出状态转移方程：dp[i] = max(dp[i-2] + nums[i], dp[i-1])。
定义目标函数：目标函数是要优化的问题特定指标。在这个问题中，我们的目标函数是打劫所有房屋所能获得的最大金额，即 dp[n-1]，其中 n 是房屋的数量。

通过找到状态转移方程 dp[i] = max(dp[i-2] + nums[i], dp[i-1]) 和定义初始条件 dp[0] 和 dp[1]，我们可以使用动态规划的方法解决"打家劫舍"问题。从 dp[0] 和 dp[1] 开始，我们可以依次计算 dp[2]、dp[3]，直到计算出 dp[n-1]，

其中 n 是房屋的数量。dp[n-1] 即为问题的最优解，即可以获得的最大金额。

这个例子展示了如何通过分析问题的最优子结构、定义状态、确定状态转移关系和目标函数，找到"打家劫舍"问题的状态转移方程。具体问题可能需要根据实际情况进行调整和拓展，但以上的步骤和思考方法可以作为指导来找到适用于动态规划问题的状态转移方程。

func rob(nums []int) int {
    n := len(nums)
    if n == 1 {
        return nums[0]
    }

    if n == 2 {
        return max(nums[0], nums[1])
    }

    dp := make([]int, n)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    for i := 2; i < n; i++ {
        dp[i] = max(dp[i - 2] + nums[i], dp[i-1])        
    }
    return dp[n-1]
}

func max(a ,b int) int {
    if a > b {
        return a
    }
    return b
}